1. Field of the Invention
The present invention relates to cryptography and, in particular, to concepts for calculating a multiplication of a multiplier and a multiplicand with regard to a modulus within a cryptographic calculation, the multiplier, the multiplicand and the modulus being parameters of the cryptographic calculation.
2. Description of the Related Art
Cryptography is one of the major applications for modular arithmetic. An essential algorithm for cryptography is the known RSA algorithm. The RSA algorithm is based on a modular exponentiation which may be represented as follows:C=Md mod (N).
Here, C is an encrypted message, M is a non-encrypted message, d is the secret key, and N is the modulus. The modulus N is usually created by multiplying two prime numbers p and q. The modular exponentiation is split into multiplications by means of the known square-and-multiply algorithm. To this end, the exponent d is split into powers of two, so that the modular exponentiation may be split into several modular multiplications. In order to be able to implement the modular exponentiation efficiently in terms of computation, the modular exponentiation is therefore split into modular multiplications, which may then be split into modular additions.
DE 3631992 discloses a cryptography method wherein modular multiplication may be accelerated using a multiplication-lookahead method and using a reduction-lookahead method. The method described in DE 3631992 C2 is also referred to as a ZDN method and will be described in more detail with regard to FIG. 18. After a starting step 900 of the algorithm, the global variables M, C and N are initialized. The aim is to calculate the following modular multiplication:Z=M*C mod N.
M is referred to as the multiplier, where C is referred to as the multiplicand. Z is the result of the modular multiplication, whereas N is the modulus.
Hereupon, different local variables are initialized, which need not be explained in further detail. Subsequently, two lookahead methods are applied. In the multiplication-lookahead method GEN_MULT_LA, a multiplication shift value sz as well as a multiplication-lookahead parameter a are calculated using different lookahead rules (910). Hereupon, the current content of the Z register is subjected to a left-shift operation by sz digits (920).
Essentially in parallel therewith, a reduction-lookahead method GEN_Mod_LA (930) is performed to calculate a reduction shift value SN and a reduction parameter b. In step 940, the current content of the modulus register, i.e. N, is shifted to the left and right, respectively, by SN digits so as to create a shifted modulus value N′. The central three-operands operation of the ZDN method takes place in step 950. Here, the intermediate result Z′ is added, after step 920, to multiplicand C, which is multiplied by the multiplication-lookahead parameter a, and to the shifted modulus N′, which is multiplied by the reduction-lookahead parameter b. Depending on the current situation, the lookahead parameters a and b may have a value of +1, 0 or −1.
A typical case is for the multiplication-lookahead parameter a to be +1, and for the reduction-lookahead parameter b to be −1, so that the multiplicand C is added to a shifted intermediate result Z′, and so that the shifted modulus N′ is subtracted therefrom. a will have a value equal to 0 if the multiplication-lookahead method allows more than a preset number of individual left shifts, i.e. if sZ is larger than the maximum admissible value of sZ, which is also referred to as k. In the event that a equals 0 and that Z′ is still fairly small due to the preceding modular reduction, i.e. to the preceding subtraction of the shifted modulus, and that Z′ is, in particular, smaller than the shifted modulus N′, no reduction need take place, so that parameter b equals 0.
Steps 910 to 950 are performed for such time until all digits of the multiplicand have been processed i.e. until m equals 0, and until a parameter n also equals 0, which parameter indicates whether the shifted modulus N′ is even larger than the original modulus N, or whether further reduction steps must be performed by subtracting the modulus from Z despite the fact that all digits of the multiplicand have already been processed.
Eventually it will also be determined whether Z is smaller than 0. If this is so, modulus N must be added to Z so as to achieve a final reduction, so that eventually the correct result Z of the modular multiplication is obtained. In a step 960, the modular multiplication by means of the ZDN method is terminated.
The multiplication shift value sZ as well as the multiplication parameter a, which are calculated by means of the multiplication-lookahead algorithm in step 910, result from the topology of the multiplier as well as from the lookahead rules used which are described in DE 3631992 C2.
The reduction shift value SN and the reduction parameter b are determined, as is also described in DE 3631992 C2, by comparing the current content of the Z register with a value 2/3×N. The name of the ZDN method is based on this comparison (ZDN=Zwei Drittel N=two thirds of N).
The ZDN method, as is depicted in FIG. 18, traces the modular multiplication back to a three-operands addition (block 950 in FIG. 18), wherein the multiplication-lookahead method and, hand in hand therewith, the reduction-lookahead method, are used for increasing the calculating-time efficiency. Therefore, an advantage in terms of calculating time may be obtained as compared with the Montgomery reduction.
The reduction-lookahead method, which is performed in block 930 of FIG. 18, will be explained below in more detail with reference to FIG. 19. Initially, in a block 1000, a reservation for the local variables, i.e. for the reduction-lookahead parameter b and the reduction shift value SN, is performed. In a block 1010, the reduction shift value SN is initialized to zero. Hereupon, the value ZDN, which equals 2/3 of modulus N, is calculated in a block 1020. This value which is determined in block 1020 is stored on the crypto-coprocessor on a register of its own, i.e. the ZDN register.
It is then determined, in a block 1030, whether the variable n equals 0, or whether the shift value SN equals −k. k is a value defining the maximum shift value specified by the hardware. In the first run, block 1030 is answered by NO, so that in a block 1040, parameter n is decremented, and so that in a block 1060, the reduction shift value is also decremented by 1. Then, in a block 1080, the variable ZDN is redefined, i.e. is defined as half its value, which may readily be achieved by a right-shift of the value found in the ZDN register. It is then established, in a block 1100, whether the absolute value of the current intermediate result is higher than the value found in the ZDN register.
This comparative operation performed in block 1100 is the central operation of the reduction-lookahead method. If the question is answered with YES, the iteration is terminated, and the reduction-lookahead parameter is defined, as is represented in block 1120. If, however, the question to be answered in block 1100 is answered with NO, an iterative backward jump is performed to examine the current values of n and SN in block 1030. If block 1030 is answered with YES at some point in the iteration, the process jumps to a block 1140, wherein the reduction parameter b is set to zero. In the three-operands operation represented in block 950 in FIG. 18, the result is that no modulus is added or subtracted, which means that the intermediate result of Z was so small that no modular reduction was necessary. In a block 1160, the variable n is then redefined, the reduction shift value SN being eventually calculated in a block 1180, which reduction shift value SN is needed, in a block 940 of FIG. 18, to perform the left shift of the modulus so as to achieve a shifted modulus.
In blocks 1200, 1220 and 1240, the current values of n and k are finally examined for further variables MAX and cur_k so as to examine the current definition of the N register to ensure that no register overshoot takes place. The further details are not relevant to the present invention but are described more fully in DE 3631992 C2.
The algorithm represented in FIGS. 18 and 19 may be implemented in terms of hardware, as is shown in FIG. 10. For the three-operands operation to be performed in block 950, an arithmetic unit 700 is required, which unit is designated as AU in FIG. 10. The latter is coupled to a register C 710 for the multiplicand, to a register N 720 for the modulus, and to a register Z 730 for the current intermediate result of the modular multiplication. It may further be seen from FIG. 10 that the result of the three-operands operation is re-fed into the Z register 730 via a feedback arrow 740. FIG. 10 also shows the interconnection of the registers. The value ZDN calculated in block 1020 of FIG. 19 must be stored in a ZDN register 750 of its own. The ZDN comparison and/or the iteration loop presented in FIG. 19 is further process-controlled by a designated control logic 760 for the ZDN comparison.
The main work of the ZDN algorithm for calculating Z:=M×C mod N therefore consists in the following two operations:    1. Calculation of the shift values sz and si for registers Z and N, so that the following equation is met:2/3N×2−si<|Z|≦4/3N×2−si and    2. Calculation of the three-operands sum:Z:=2szZ+a C+b×2sz−si N
Multiplication-lookahead parameter a and reduction-lookahead parameter b may, as is known, take on values of −1, 0 and +1.
It shall be pointed out that the intermediate result Z, the multiplicand C and the modulus N of long numbers, i.e. numbers whose numbers of digits and/or bits may easily be larger than 512, it being possible that these figures have up to more than 2048 digits.
The known method described above for performing the modular multiplication also comprises the following three-operands addition, which has been slightly altered, of the following form:N:=N*2snZ:=Z*2sz+vc*C+vn*N.
In the above equations, sz designates the shift value of the intermediate result Z, as is calculated from the known Booth method, i.e. from the multiplication-lookahead method. sn designates the shift value of N calculated as set forth above.
In a practical implementation, the shift values sz and Sn must not be infinitely high, especially as shifters for shifting long numbers are provided for this purpose, which may only accomplish a bit shift, in a long-number register, to a maximum shift value. In this manner, a shift value sz of between 0 and 5 is made possible in a cryptography processor operating in accordance with the known ZDN method. With regard to the shift of the modulus, a shift value between −3 and +3 is used.
The limited shift values have the drawback that, e.g., the shift value sz for shifting the intermediate result Z from a previous iteration step is often too small for a current iteration step. To be precise, this is the case if the multiplication-lookahead algorithm establishes that the nature of the multiplier is such that, for example, a shift value larger than 5 is possible. This applies if, depending on the lookahead rule, e.g. more than 5 subsequent zeros come up in the multiplier. If it is contemplated that the multiplier M has 1024 or even 2048 bits, this situation may easily occur relatively frequently. Due to the limited shift value, the known ZDN method will react, in this “special case”, by performing a three-operands operation, to be precise with the maximum shift value, however by setting the multiplication-lookahead parameter vc to 0, i.e. by not adding anything to the multiplicand in this step. In the next iteration step, a new multiplication shift value sz is calculated, which, if it is larger than the maximum shift value Szmax, is again limited by the maximum shift value, which again leads to a degenerated “three-operands addition”, wherein the multiplicand is again not added, i.e. wherein only the shifted intermediate result as well as the shifted modulus are added taking into consideration the sign for the modulus.
It may be seen from the above consideration that in such a special case, when the multiplication-lookahead algorithm would permit a large shift, same cannot be implemented with maximum efficiency, which is due to the limited shift magnitude Szmax.
The known ZDN method is therefore not capable of making use of the full increase in efficiency of the multiplication-lookahead method. In order to achieve an increase in efficiency, a shifter enlargement would have to be performed in the known ZDN method, which shifter enlargement, however, leads to the fact, in particular in integrated circuits for chip cards, that more chip area is needed, which is not always tolerable due to tight chip area specifications furnished by chip-card manufacturers, and/or which may lead to considerable price rises.
It shall be pointed out at this stage that in particular in the field of cryptography processors, there is an extremely competitive market where even small price differences will lead to one provider surviving while another provider will not survive. This is due to the fact that processors for chip cards are a mass product, since chip cards are typically manufactured in large numbers.
On the other hand, there are considerable security demands placed on chip-card processors, since chip cards are typically in the hand of users, i.e. also in the hand of attackers which are in full control of the chip-card processor to be attacked. Therefore, security demands placed upon cryptography algorithms are more and more on the increase, which may be seen, for example, in the fact that for increasing the security of the RSA algorithm, the operands are now not only required to have a length of, e.g., 1024, but have to be 2048 bits long.
Nevertheless, the overall area taken up by the processor is preset by the chip-card manufacturer. This means that a manufacturer of chip-card processors must accommodate on a preset area calculating units and memories requiring a large amount of space. By contrast, cryptography algorithms which are more and more complicated also need more and more working memory, so that an enlargement of a calculating unit to the effect that, for example, a larger shifter is installed, is often not tolerable for this reason. That is, if more chip area were attributed to the calculating unit, i.e., for example, to a shifter, a smaller amount of working memory could, in turn, be implemented on the specified chip area, which in turn leads to the fact that certain highly complicated cryptography algorithms cannot be performed at all and/or are slower in terms of calculation than when they are performed and implemented by products of competitors.